//
// Created by 高森森 on 2022/10/11.
//

#ifndef LEETCODE_SOLUTION_20_H
#define LEETCODE_SOLUTION_20_H

#include<bits/stdc++.h>
using namespace std;
const int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
class solution_20 {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int>result;
        vector<vector<int>>flag(matrix.size(),vector<int>(matrix[0].size(),0));
        int status=0;
        dfs(matrix,flag,result,0,0,status);
        for(int num:result){
            cout<<num<<" ";
        }
        return result;
    }
    void dfs(vector<vector<int>>&matrix,vector<vector<int>>&flag,vector<int> &result,int i,int j,int status){
        flag[i][j]=1;
        result.push_back(matrix[i][j]);
        if(result.size()==matrix.size()*matrix[0].size()){
            return ;
        }
        int nextI=i+direction[status][0];
        int nextJ=j+direction[status][1];
        if(nextI<0||nextI>=matrix.size()||nextJ<0||nextJ>=matrix[0].size()||flag[nextI][nextJ]==1){
            status=(status+1)%4;
        }
        dfs(matrix,flag,result,i+direction[status][0],j+direction[status][1],status);
    }
};


#endif //LEETCODE_SOLUTION_20_H
